<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,200分)- 计算误码率（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>误码率是最常用的数据通信传输质量指标。它可以理解为“在多少位数据中出现一位差错”。</p> 
<p>移动通信网络中的误码率主要是指比特误码率&#xff0c;其计算公式如下: 比特误码率&#61;错误比特数/传输总比特数&#xff0c;</p> 
<p>为了简单&#xff0c;我们使用字符串来标识通信的信息&#xff0c;一个字符错误了&#xff0c;就认为出现了一个误码</p> 
<p>输入一个标准的字符串&#xff0c;和一个传输后的字符串&#xff0c;计算误码率</p> 
<p>字符串会被压缩&#xff0c;<br /> 例:“2A3B4D5X1Z”表示&#34;AABBBDDDDXXXXXZ&#34;<br /> 用例会保证两个输入字符串解压后长度一致&#xff0c;解压前的长度不一定一致</p> 
<p>每个生成后的字符串长度&lt;100000000。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>两行&#xff0c;分别为两种字符串的压缩形式。</p> 
<p>每行字符串 (压缩后的) 长度&lt;100000</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>一行&#xff0c;错误的字等数量/展开后的总长度</p> 
<p></p> 
<h4>备注</h4> 
<p>注意&#xff1a;展开后的字符串不含数字</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">3A3B<br /> 2A4B</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1/6</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">5Y5Z<br /> 5Y5Z</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">0/10</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">4Y5Z<br /> 9Y</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">5/9</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题最简单的做法就是将压缩字符串解压&#xff0c;然后利用一次for循环&#xff0c;对比两个等长的压缩字符串&#xff0c;看有多少个位置的字符不相同。</p> 
<p>但是本题解压后的字符串&#xff0c;最大长度为1 0000 0000&#xff0c;这个数量级对于O(n)时间复杂度来说也会超时。</p> 
<p>另外&#xff0c;解压后的字符串&#xff0c;内存会占到 1 0000 0000 * 1 byte ≈ 96M, 两个字符串就是将近200M&#xff0c;这种方案在内存上也是不友好的。</p> 
<p></p> 
<p>因此&#xff0c;我们不应该优先考虑上面方案&#xff0c;而是应该考虑基于压缩字符串找不同字符数量。</p> 
<p></p> 
<p>我的解题思路如下&#xff1a;</p> 
<p>定义两个变量diff和same&#xff0c;分别用于记录输入的两个字符串中不同字符的数量&#xff0c;以及相同字符的数量。</p> 
<p>以用例1举例&#xff1a;</p> 
<p><img alt="" height="90" src="https://img-blog.csdnimg.cn/0c5e331510cd455da7dcfcfe5030c4e6.png" width="199" /></p> 
<p>我们可以比较s1,s2的头部压缩字符串&#xff0c;其中&#xff0c;</p> 
<ul><li>s1的头部压缩字符串是3A</li><li>s2的头部压缩字符串是2A</li></ul> 
<p>压缩字符串由两部分组成&#xff1a;压缩次数num &#43; 压缩字符c</p> 
<ul><li>s1的头部压缩字符串是3A&#xff0c;即num1 &#61; 3&#xff0c;c1 &#61; &#39;A&#39;</li><li>s2的头部压缩字符串是2A&#xff0c;即num2 &#61; 2&#xff0c;c2 &#61; &#39;A&#39;</li></ul> 
<p>当前s1,s2的头部压缩字符串是不等长的&#xff0c;因此我们应该取二者最小长度作为比对长度&#xff0c;即</p> 
<blockquote> 
 <p>compareCount &#61; min(num1, num2)</p> 
</blockquote> 
<ul><li>如果c1 &#61;&#61; c2的话&#xff0c;则compareCount就是相同字符数量&#xff0c;即same &#43;&#61; compareCount</li><li>如果c1 !&#61; c2的话&#xff0c;则compareCount就是不同字符数量&#xff0c;即diff &#43;&#61; compareCount</li></ul> 
<p> 之后&#xff0c;继续检查num1, num2的大小关系&#xff0c;如果二者不等的话&#xff1a;</p> 
<ul><li>如果 num1 &gt; num2&#xff0c;则说明s1的头部压缩字符串没有用完&#xff0c;我们应该将剩余部分重新退回s1头部&#xff0c;即将 (num1 - num2) &#43; c1 拼接回 s1头部</li><li>如果 num1 &lt; num2&#xff0c;则说明s2的头部压缩字符串没有用完&#xff0c;我们应该将剩余部分重新退回s2头部&#xff0c;即将 (num2 - num1) &#43; c2 拼接回 s2头部</li></ul> 
<p>然后&#xff0c;s1&#xff0c;s2变为了</p> 
<p><img alt="" height="106" src="https://img-blog.csdnimg.cn/6c0261d3dfc14fe681e708aed6f41078.png" width="211" /></p> 
<p>然后继续&#xff0c;按照上面逻辑处理&#xff0c;直到s1或s2为空。</p> 
<p></p> 
<p>当然&#xff0c;为了避免频繁的字符串操作&#xff0c;我们可以将s1,s2解析为灵活度更高的链表&#xff0c;链表节点元素即为压缩字符串转化的对象&#xff0c;类似于下面这种</p> 
<blockquote> 
 <p>{<!-- --><br />     num: 3,<br />     c: &#39;A&#39;<br /> }</p> 
</blockquote> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61; 2) {
    console.log(getResult(lines[0], lines[1]));
    lines.length &#61; 0;
  }
});

function getResult(s1, s2) {
  const link1 &#61; getZipStrLink(s1);
  const link2 &#61; getZipStrLink(s2);

  let diff &#61; 0;
  let same &#61; 0;

  while (link1.length &gt; 0) {
    const [num1, c1] &#61; link1.shift();
    const [num2, c2] &#61; link2.shift();

    const compareCount &#61; Math.min(num1, num2);

    if (c1 !&#61; c2) {
      diff &#43;&#61; compareCount;
    } else {
      same &#43;&#61; compareCount;
    }

    if (num1 &gt; num2) {
      link1.unshift([num1 - num2, c1]);
    } else if (num1 &lt; num2) {
      link2.unshift([num2 - num1, c2]);
    }
  }

  return &#96;${diff}/${diff &#43; same}&#96;;
}

function getZipStrLink(s) {
  const link &#61; [];

  const num &#61; [];

  for (let i &#61; 0; i &lt; s.length; i&#43;&#43;) {
    const c &#61; s[i];

    if (c &gt;&#61; &#34;0&#34; &amp;&amp; c &lt;&#61; &#34;9&#34;) {
      num.push(c);
    } else {
      const zipStr &#61; [parseInt(num.join(&#34;&#34;)), c];
      link.push(zipStr);
      num.length &#61; 0;
    }
  }

  return link;
}
</code></pre> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  static class ZipStr {
    int num;
    char c;

    public ZipStr(int num, char c) {
      this.num &#61; num;
      this.c &#61; c;
    }
  }

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String s1 &#61; sc.nextLine();
    String s2 &#61; sc.nextLine();

    System.out.println(getResult(s1, s2));
  }

  public static String getResult(String s1, String s2) {
    LinkedList&lt;ZipStr&gt; link1 &#61; getZipStrLink(s1);
    LinkedList&lt;ZipStr&gt; link2 &#61; getZipStrLink(s2);

    int diff &#61; 0;
    int same &#61; 0;

    while (link1.size() &gt; 0) {
      ZipStr zipStr1 &#61; link1.removeFirst();
      ZipStr zipStr2 &#61; link2.removeFirst();

      int compareCount &#61; Math.min(zipStr1.num, zipStr2.num);

      if (zipStr1.c !&#61; zipStr2.c) {
        diff &#43;&#61; compareCount;
      } else {
        same &#43;&#61; compareCount;
      }

      if (zipStr1.num &gt; compareCount) {
        zipStr1.num -&#61; compareCount;
        link1.addFirst(zipStr1);
        continue;
      }

      if (zipStr2.num &gt; compareCount) {
        zipStr2.num -&#61; compareCount;
        link2.addFirst(zipStr2);
      }
    }

    return diff &#43; &#34;/&#34; &#43; (diff &#43; same);
  }

  public static LinkedList&lt;ZipStr&gt; getZipStrLink(String s) {
    LinkedList&lt;ZipStr&gt; link &#61; new LinkedList&lt;&gt;();

    StringBuilder num &#61; new StringBuilder();

    for (int i &#61; 0; i &lt; s.length(); i&#43;&#43;) {
      char c &#61; s.charAt(i);

      if (c &gt;&#61; &#39;0&#39; &amp;&amp; c &lt;&#61; &#39;9&#39;) {
        num.append(c);
      } else {
        link.add(new ZipStr(Integer.parseInt(num.toString()), c));
        num &#61; new StringBuilder();
      }
    }

    return link;
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
s1 &#61; input()
s2 &#61; input()


def getZipStrLink(s):
    link &#61; []

    num &#61; []

    for i in range(len(s)):
        c &#61; s[i]

        if c.isdigit():
            num.append(c)
        else:
            link.append([int(&#34;&#34;.join(num)), c])
            num.clear()

    return link


# 算法入口
def getResult():
    link1 &#61; getZipStrLink(s1)
    link2 &#61; getZipStrLink(s2)

    diff &#61; 0
    same &#61; 0

    while len(link1) &gt; 0:
        num1, c1 &#61; link1.pop(0)
        num2, c2 &#61; link2.pop(0)

        compareCount &#61; min(num1, num2)

        if c1 !&#61; c2:
            diff &#43;&#61; compareCount
        else:
            same &#43;&#61; compareCount

        if num1 &gt; num2:
            link1.insert(0, [num1 - num2, c1])
        elif num1 &lt; num2:
            link2.insert(0, [num2 - num1, c2])

    return f&#34;{diff}/{diff &#43; same}&#34;


# 算法调用
print(getResult())</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

#define MAX_SIZE 100000
#define MIN(a, b) (a) &lt; (b) ? (a) : (b)

typedef struct {
    int num;
    char c;
} ZipStr;

typedef struct ListNode {
    ZipStr *ele;
    struct ListNode *next;
} Node;

typedef struct List {
    Node *head;
    Node *tail;
    int size;
} LinkedList;

char s1[MAX_SIZE];
char s2[MAX_SIZE];

LinkedList *new_LinkedList();

void addFirst_LinkedList(LinkedList *link, ZipStr *ele);

void addLast_LinkedList(LinkedList *link, ZipStr *ele);

ZipStr *removeFirst_LinkedList(LinkedList *link);

LinkedList *getZipStrLink(char *s);

int main() {
    gets(s1);
    gets(s2);

    LinkedList *link1 &#61; getZipStrLink(s1);
    LinkedList *link2 &#61; getZipStrLink(s2);

    int diff &#61; 0;
    int same &#61; 0;

    while (link1-&gt;size &gt; 0) {
        ZipStr *zipStr1 &#61; removeFirst_LinkedList(link1);
        ZipStr *zipStr2 &#61; removeFirst_LinkedList(link2);

        int compareCount &#61; MIN(zipStr1-&gt;num, zipStr2-&gt;num);

        if (zipStr1-&gt;c !&#61; zipStr2-&gt;c) {
            diff &#43;&#61; compareCount;
        } else {
            same &#43;&#61; compareCount;
        }

        if (zipStr1-&gt;num &gt; compareCount) {
            zipStr1-&gt;num -&#61; compareCount;
            addFirst_LinkedList(link1, zipStr1);
        }

        if (zipStr2-&gt;num &gt; compareCount) {
            zipStr2-&gt;num -&#61; compareCount;
            addFirst_LinkedList(link2, zipStr2);
        }
    }

    char res[1000];
    sprintf(res, &#34;%d/%d&#34;, diff, diff &#43; same);

    printf(&#34;%s&#34;, res);

    return 0;
}

LinkedList *getZipStrLink(char *s) {
    LinkedList *link &#61; new_LinkedList();

    char num[100] &#61; {&#39;\0&#39;};

    for (int i &#61; 0; i &lt; strlen(s); i&#43;&#43;) {
        if (s[i] &gt;&#61; &#39;0&#39; &amp;&amp; s[i] &lt;&#61; &#39;9&#39;) {
            strcat(num, (char[]) {s[i], &#39;\0&#39;});
        } else {
            ZipStr *ele &#61; (ZipStr *) malloc(sizeof(ZipStr));
            ele-&gt;num &#61; atoi(num);
            ele-&gt;c &#61; s[i];

            memset(num, &#39;\0&#39;, 100);

            addLast_LinkedList(link, ele);
        }
    }

    return link;
}

LinkedList *new_LinkedList() {
    LinkedList *link &#61; (LinkedList *) malloc(sizeof(LinkedList));

    link-&gt;head &#61; NULL;
    link-&gt;tail &#61; NULL;
    link-&gt;size &#61; 0;

    return link;
}

void addFirst_LinkedList(LinkedList *link, ZipStr *ele) {
    Node *node &#61; (Node *) malloc(sizeof(Node));
    node-&gt;ele &#61; ele;
    node-&gt;next &#61; NULL;

    if (link-&gt;size &#61;&#61; 0) {
        link-&gt;head &#61; node;
        link-&gt;tail &#61; node;
    } else {
        Node *oldHead &#61; link-&gt;head;
        link-&gt;head &#61; node;
        link-&gt;head-&gt;next &#61; oldHead;
    }

    link-&gt;size&#43;&#43;;
}

void addLast_LinkedList(LinkedList *link, ZipStr *ele) {
    Node *node &#61; (Node *) malloc(sizeof(Node));
    node-&gt;ele &#61; ele;
    node-&gt;next &#61; NULL;

    if (link-&gt;size &#61;&#61; 0) {
        link-&gt;head &#61; node;
        link-&gt;tail &#61; node;
    } else {
        link-&gt;tail-&gt;next &#61; node;
        link-&gt;tail &#61; node;
    }

    link-&gt;size&#43;&#43;;
}

ZipStr *removeFirst_LinkedList(LinkedList *link) {
    if (link-&gt;size &gt; 0) {
        Node *removed &#61; link-&gt;head;

        if (link-&gt;size &#61;&#61; 1) {
            link-&gt;head &#61; NULL;
            link-&gt;tail &#61; NULL;
        } else {
            link-&gt;head &#61; link-&gt;head-&gt;next;
        }

        link-&gt;size--;

        ZipStr *zipStr &#61; (ZipStr *) malloc(sizeof(ZipStr));
        zipStr-&gt;num &#61; removed-&gt;ele-&gt;num;
        zipStr-&gt;c &#61; removed-&gt;ele-&gt;c;

        free(removed);

        return zipStr;
    }

    return NULL;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>